import java.util.LinkedList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-14
 * Time:11:37
 */
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
public class Test {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead==null){
            return null;
        }
        ListNode head=new ListNode(-1);
        ListNode head1=head;
        ListNode cur=pHead;
        ListNode heado=new ListNode(-1);
        ListNode head2=heado;
        while (cur!=null){
            //小于的话添加新的链表中
            if(cur.val<x){
                //添加
                head1.next=cur;
                head1=head1.next;
            }else {
                //旧连表继续添加
                head2.next=cur;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head==null){
            return heado.next;
        }
        head1.next=heado.next;
        if(head2!=null){
            head2.next=null;
        }
        return head.next;
    }

    public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();
        LinkedList<Integer> linkedList=new LinkedList<>();
    }
}
